package simple.string;

/**
 * <a href="https://leetcode-cn.com/problems/longest-common-prefix">14. 最长公共前缀</a>
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串""。
 * 示例 1：
 *   输入：strs = ["flower","flow","flight"]
 *   输出："fl"
 * 示例 2：
 *   输入：strs = ["dog","racecar","car"]
 *   输出：""
 *   解释：输入不存在公共前缀。
 * 提示：
 *   0 <= strs.length <= 200
 *   0 <= strs[i].length <= 200
 *   strs[i] 仅由小写英文字母组成
 * 解题思路：
 *   1.当输入数组长度为0，直接返回空字符串
 *   2.以数组中第一个字符串为准，循环截取子串，如：strs[0]="abc"，第一次取“a”，第二次取“ab“...直到取完整个字符串
 *   3.每次循环都遍历一次数组，每个元素都与截取子串作startWith匹配，若不匹配，则直接返回子串除去最后一个字符后的字符串
 *   4.若无一不匹配的，直接返回数组第一个字符串
 * @author 刘学松
 * @date 2021/3/2 19:09
 */
public class 最长公共前缀 {
    public static void main(String[] args) {
        String[] strs = {"flower","flow","flight"};
        System.out.println(longestCommonPrefix1(strs));
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String result = strs[0];
        for (String str: strs) {
            while (!str.startsWith(result)) {
                result = result.substring(0, result.length()-1);
            }
        }
        return result;
    }

    public static String longestCommonPrefix1(String[] strs) {
        int length = strs.length;
        if (length == 0) {
            return "";
        }
        String result = "";
        for (int i = 1; i <= strs[0].length(); i++) {
            result = strs[0].substring(0, i);
            for (String str : strs) {
                if (!str.startsWith(result)) {
                    return result.substring(0, result.length()-1);
                }
            }
        }
        return result;
    }
}
